import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-05-13
 * Time: 11:53
 */


//
//class Solution1 {
//    public int[] nextLargerNodes(ListNode head) {
//        List<Integer> list = new ArrayList<>();
//        //链表元素存储到集合中
//        while (head != null) {
//            list.add(head.val);
//            head = head.next;
//        }
//        //栈中存储的是元素的下标，并且从栈底到栈顶元素在集合中对应的
//        //值是从大到小的
//        Stack<Integer> stack = new Stack<>();
//        int[] res = new int[list.size()];
//        for (int i = 0; i < list.size(); i++) {
//            while (!stack.empty() && list.get(stack.peek()) < list.get(i)) {
//                //如果栈顶元素对应的值小于当前值，说明栈顶元素遇到了比他小的
//                int index = stack.pop();
//                res[index] = list.get(i);
//            }
//            stack.push(i);
//        }
//        return res;
//    }
//}
//class ListNode {
//    public int val;
//    public ListNode next;
//    public ListNode(int val){
//        this.val = val;
//    }
//}
class Solution6 {
    public int[] nextLargerNodes(ListNode head) {
        ListNode p = head;
        Stack<Integer> stack = new Stack<>();//创建栈
        int m = 0;
        while (p != null) {
            m++;//记录链表长度
            p = p.next;
        }
        p = head;
        int[] nums = new int[m];
        int[] res = new int[m];
        for (int i=0;i<m;i++) {//将链表的val全部放到数组nums里面
            nums[i] = p.val;
            p = p.next;
        }

        for (int i=0;i<m;i++) {
            //栈不为空并且栈顶元素小于当前元素，就找到了下一个更大的节点
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                res[stack.peek()] = nums[i];
                stack.pop();
            }
            //如果栈为空就证明栈中刚开始栈中没有元素，所以就放入栈中
            stack.push(i);
        }
        return res;
    }
}

//我们如果发现栈为空我们就将其数组下标放入栈中，然后遍历下一个元素，
//        如果发现栈不为空并且栈中下标的元素<当前遍历的元素，
//        这就证明找到了下一个更大的节点那就把这个元素放到对应的下标里面去，
//        并且将这个元素的下标弹出栈，如果没有找到也许可能下一个更大的节点在后面，我们就将这个下标放入栈中，
//        后面如果有更大的元素都有可能是前面元素的下一个更大节点，所以我们要使用循环，一次将栈中对应的下标，放入这个更大的元素

class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val){
        this.val = val;
    }
    public ListNode(){

    }
}
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //先把两个链表中的元素分别放到两个栈当中，然后，
        //一一进行相加，最后将节点进行头插即可
        //先有两个栈
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        //先将链表l1进行入栈
        while(l1!=null){
            stack1.push(l1.val);
            l1 = l1.next;
        }
        //在将链表l2进行入栈
        while(l2!=null){
            stack2.push(l2.val);
            l2 = l2.next;
        }
        ListNode head = null;
        int carry =0;
        while(!stack1.isEmpty()||!stack2.isEmpty()){
            //将两个数相加头插到新的链表当中去
            int sum =0;
            if(!stack1.isEmpty()){
                sum+=stack1.peek();
                stack1.pop();
            }
            if(!stack2.isEmpty()){
                sum+=stack2.peek();
                stack2.pop();
            }
            if(head==null){
                sum+=carry;
                head = new ListNode(sum%10);
                carry=sum/10;
            }else {
                sum+=carry;
                ListNode cur = new ListNode(sum%10);
                cur.next = head;
                head = cur;
                carry=sum/10;
            }
        }
        if(carry>0){
            ListNode cur = new ListNode(carry);
            cur.next = head;
            head = cur;
        }
        return head;
    }
}
//
//class Solution {
//    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//        //先把两个链表中的元素分别放到两个栈当中，然后，
//        //一一进行相加，最后将节点进行头插即可
//        //先有两个栈
//        Stack<Integer> stack1 = new Stack<>();
//        Stack<Integer> stack2 = new Stack<>();
//        //先将链表l1进行入栈
//        while(l1!=null){
//            stack1.push(l1.val);
//            l1 = l1.next;
//        }
//        //在将链表l2进行入栈
//        while(l2!=null){
//            stack2.push(l2.val);
//            l2 = l2.next;
//        }
//        int carry =0;
//        ListNode cur =null;
//        while(!stack1.isEmpty()||!stack2.isEmpty()){
//            //将两个数相加头插到新的链表当中去
//            int sum =0;
//            if(!stack1.isEmpty()){
//                sum+=stack1.peek();
//                stack1.pop();
//            }
//            if(!stack2.isEmpty()){
//                sum+=stack2.peek();
//                stack2.pop();
//            }
//            sum+=carry;
//            ListNode node = new ListNode(sum%10);
//            node.next = cur;
//            cur = node;
//            carry=sum/10;
//        }
//        if(carry>0){
//            ListNode node = new ListNode(carry);
//            node.next = head;
//            cur =node;
//        }
//        return cur;
//    }
//}

class Solution7 {
    public boolean backspaceCompare(String s, String t) {
        int skipS =0;
        int skipT =0;
        int i= s.length()-1;
        int j= t.length()-1;
        while(i>=0||j>=0){
            //先来判断i指针指向的s字符串
            while(i>=0){
                if(s.charAt(i)=='#'){
                    ++skipS;
                    --i;
                }else if(skipS>0){
                    --skipS;
                    --i;
                }else {
                    break;
                }
            }
            while(j>=0){
                if(t.charAt(j)=='#'){
                    ++skipT;
                    --j;
                }else if(skipT>0){
                    --skipT;
                    --j;
                }else {
                    break;
                }
            }
            //开始s和t进行比较
            if (i >= 0 && j >= 0) {
                if (s.charAt(i) != t.charAt(j)) {
                    return false;
                }
            }else {
                if(i>=0&&j<0||j>=0&&i<0){
                    return false;
                }
            }
            i--;
            j--;
        }
        return true;
    }
}

class Solution9 {
    public boolean backspaceCompare(String s, String t) {
        //使用栈解决问题
        Stack<Character> stack1 = new Stack<>();
        Stack<Character> stack2 = new Stack<>();
        //分别遍历两个字符串,如果是字符就入栈，#号就出栈
        int s1 = s.length()-1;
        int t1 = t.length()-1;
        while(s1>=0){
            if(!stack1.isEmpty()&&s.charAt(s1)=='#'){
                stack1.pop();
            }else{
                stack1.push(s.charAt(s1));
            }
            s1--;
        }
        while(t1>=0){
            if(!stack2.isEmpty()&&t.charAt(t1)=='#'){
                stack2.pop();
            }else{
                stack2.push(t.charAt(t1));
            }
            t1--;
        }
        //比较栈上两个字符相不相等
        while(!stack2.isEmpty()&&!stack1.isEmpty()){
            if(stack1.peek()==stack2.peek()){
                stack1.pop();
                stack2.pop();
            }else {
                return false;
            }
        }
        return true;

    }
}
class Solution10 {
    public boolean backspaceCompare(String s, String t) {
        Stack<Character> stackS = new Stack<>();
        Stack<Character> stackT = new Stack<>();
        char[] charS = s.toCharArray();
        char[] charT = t.toCharArray();
        for(int i =0;i<charS.length;++i){
            if(!stackS.isEmpty()&&charS[i]=='#'){
                stackS.pop();
            }else if(charS[i]>0) {
                stackS.push(charS[i]);
            }
        }

        for(int i =0;i<charT.length;++i){
            if(!stackT.isEmpty()&&charT[i]=='#'){
                stackT.pop();
            }else if(charT[i]>0) {
                stackT.push(charT[i]);
            }
        }

        while(!stackS.isEmpty()&&!stackT.isEmpty()){
            if(stackS.peek()!=stackT.peek()){
                return false;
            }else {
                stackT.pop();
                stackS.pop();
            }
        }
        return stackS.isEmpty()&&stackT.isEmpty();
    }
}
public class TestDemo {


    public static void main(String[] args) {
        Solution10 solution10 = new Solution10();
        solution10.backspaceCompare("y#fo##f","y#f#o##f");
    }


    public static void main5(String[] args) {
        Solution solution = new Solution();
//        ListNode node1 = new ListNode(7);
//        ListNode node2 = new ListNode(2);
//        ListNode node3 = new ListNode(4);
//        ListNode node4 = new ListNode(3);
//        ListNode node5 = new ListNode(5);
//        ListNode node6 = new ListNode(6);
//        ListNode node7 = new ListNode(4);
//        node1.next = node2;
//        node2.next =node3;
//        node3.next=node4;
//        node4.next=null;
//        node5.next = node6;
//        node6.next=node7;
//        node7.next=null;
        ListNode node1 = new ListNode(5);
        ListNode node2 = new ListNode(5);
        node1.next =null;
        node2.next =null;

        solution.addTwoNumbers(node1,node2);
    }

}
